package com.beautiful.xin.other;

import com.google.common.collect.Sets;
import org.apache.commons.math3.analysis.function.Max;
import org.omg.CORBA.INTERNAL;

import java.util.HashSet;
import java.util.TreeSet;
import java.util.logging.SocketHandler;

/**
 * @author xuqingxin 2021/7/25 12:03 下午
 */
public class ProcessTest {
    public static void main(String[] args) {
        // 暴力 非最优解
        int[] arr = {2, 3, 4};
        int m = 3;

        Integer integer1 = max1(arr, m);
        Integer integer = max2(arr, m);

        System.out.println("integet1:" + integer1 + "|||integer2:" + integer);
        System.out.println(max4(arr, m));
    }

    public static int max4(int[] arr, int m) {
        if (arr.length == 1) {
            return arr[0] % m;
        }
        int mid = (arr.length - 1) / 2;
        TreeSet<Integer> s1 = new TreeSet<>();
        process4(arr, 0, 0, mid, m, s1);
        TreeSet<Integer> s2 = new TreeSet<>();
        process4(arr, mid + 1, 0, arr.length - 1, m, s2);

        int ans = 0;
        for (Integer left : s1) {
            ans = Math.max(ans, left + s2.floor(m - 1 - left));
        }
        return ans;
    }

    private static void process4(int[] arr, int index, int sum, int end, int m, TreeSet<Integer> s1) {
        if (index == end + 1) {
            s1.add(sum % m);
        } else {
            process4(arr, index + 1, sum, end, m, s1);
            process4(arr, index + 1, sum + arr[index], end, m, s1);
        }
    }


    private static Integer max2(int[] arr, int m) {
        int sum = 0;
        int N = arr.length;
        for (int i = 0; i < N; i++) {
            sum += arr[i];
        }
        boolean[][] dp = new boolean[N][sum + 1];

        for (int i = 0; i < N; i++) {
            dp[i][0] = true;
        }

        dp[0][arr[0]] = true;

        for (int i = 1; i < N; i++) {
            for (int j = 1; j < sum; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - arr[i] >= 0) {
                    dp[i][j] = dp[i][j] | dp[i - 1][j - arr[i]];
                }
            }
        }

        int ans = 0;
        for (int j = 0; j <= sum; j++) {
            if (dp[N - 1][j]) {
                ans = Math.max(ans, j % m);
            }
        }
        return ans;
    }

    /**
     * 给定一个非负数组arr, 和一个正数m, 返回arr的所有子序列中累加和%m之后的最大值
     *
     * @param arr
     * @param m
     * @return
     */
    public static int max1(int[] arr, int m) {
        HashSet<Integer> set = Sets.newHashSet();
        process(arr, 0, 0, set);
        int max = 0;
        for (Integer sum : set) {
            max = Math.max(sum, max);
        }
        return max;
    }

    /**
     * @param arr   数组
     * @param index 要  或 不要
     * @param sum   累加和
     * @param set   所有形成的累加和放到set中
     */
    private static void process(int[] arr, int index, int sum, HashSet<Integer> set) {
        if (index == arr.length) {
            set.add(sum);
        } else {
            process(arr, index + 1, sum, set);
            process(arr, index + 1, sum + arr[index], set);
        }
    }
}
